package sort;

import com.alibaba.fastjson.JSON;

import java.util.HashMap;
import java.util.Vector;

public class Sort {

    public static void main(String[] args) {
//        int[] array = new int[10000];
//        for (int j = 0; j < array.length; j++) {
//            array[j] = (int) (Math.random() * 10000);
//        }
        long start;
        long end;

        int[] array = {1,9,6,2,4,3};
//        start = System.currentTimeMillis();
//        bubbleSort(array);
//        end = System.currentTimeMillis();
//        out(array);
//        System.out.println("bubbleSort time consuming：" + (end - start) + " ms");

        start = System.currentTimeMillis();
        insertSort2(array);
        end = System.currentTimeMillis();
        out(array);
        System.out.println("bubbleSort time consuming：" + (end - start) + " ms");
    }

    private static void out(int[] array) {
        System.out.println(array.length <= 10 ? JSON.toJSONString(array)+" " : "");
    }

    public static void bubbleSort(int[] array) {
        int len = array.length;
//        for (int i = 0; i < len; i++) {
//            for (int j = i; j < len; j++) {
//                if (array[i] > array[j]) {
//                    int temp = array[j];
//                    array[j] = array[i];
//                    array[i] = temp;
////                    System.out.println("i: " + i + " " + JSON.toJSONString(array));
//                }
//            }
//        }
        for (int i = 0; i < len; i++) {
            for (int j = 1; j < len; j++) {
                if (array[j - 1] > array[j]) {
                    int temp = array[j - 1];
                    array[j - 1] = array[j];
                    array[j] = temp;
                }
            }
        }

    }

    /**
     * 1、把数和InsertNode比较，然后将大数往前移；将InsertNode移到比较最后一次的位置
     *
     *
     * @param array
     */
    public static void insertSort(int[] array) {
        int insertNode;
        int j;
        for (int i = 1; i < array.length; i++) {
            insertNode = array[i];
            j = i - 1;
            while (j >= 0 && insertNode < array[j]) {
                array[j + 1] = array[j];
                j--;
            }
            array[j + 1] = insertNode;
        }
    }

    public static void insertSort2(int[] array) {
        int insertNode;
        int j;
//        for (int i = 1; i < array.length; i++) {
//            insertNode = array[i];
//            j = i - 1;
//            while (j >= 0 && insertNode < array[j]) {
//                array[j+1] = array[j];
//                j--;
//            }
//            array[j+1] = insertNode;
//        }
        for (int i = 1; i < array.length; i++) {
            insertNode = array[i];
            j = i - 1;
            while (j >= 0 && array[j] > insertNode) {
                array[j+1] = array[j];
                --j;
            }
            array[j+1] = insertNode;
        }

    }

    public static void selectSort(int[] array) {
        
    }

}
